package com.likou;

/**
 * Author: 陈桂明
 * Date: 2025/9/3 10:07
 * Description: q45
 */
public class q45 {

    // // 广度优先搜索
    // public int jump(int[] nums) {
    //     int left = 0;
    //     int right = 0;
    //     int max = 0;
    //     int ans = 0;
    //
    //     while (right < nums.length - 1) {
    //         for (int i = left; i <= right; i++) {
    //             max = Math.max(max, i + nums[i]);
    //         }
    //
    //         left = right + 1;
    //         right = max;
    //         ans++;
    //     }
    //
    //     return ans;
    // }


    public int jump(int[] nums) {
        int end = 0;
        int max = 0;
        int ans = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            max = Math.max(max, nums[i] + i);

            if (i == end) {
                end = max;
                ans++;
            }

        }

        return ans;
    }
}
